#include <iostream>
#include <vector>
#include<string>
#include <algorithm>

using namespace std;

class Solution 
{
public:
    bool isMatch(string s, string p) 
    {
        int n = s.size(),m = p.size();
        vector<vector<bool>>dp(n + 1,vector<bool>(m + 1));
        //初始化
        dp[0][0] = true;
        s = " " + s;
        p = " " + p;

        for(int j = 2;j <= m;j+=2)
            if(p[j] == '*') dp[0][j] = true;
            else break;

        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= m;j++)
            {
                if((s[i] == p[j] || p[j] == '.') && dp[i-1][j-1]) dp[i][j] = true;
                else if(p[j] == '*') dp[i][j] = dp[i][j-2] || ((p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j]);
            }
        }
        return dp[n][m];
    }
};